package leetcode.DFS_BFS;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author mazouri
 * @create 2021-09-21 23:34
 */
public class MazeBFS {
    int[] dX = {0, 0, 1, -1};
    int[] dY = {1, -1, 0, 0};
    int[][] maze;
    //访问过为true
    boolean[][] visited;
    Queue<Point> queue = new LinkedList<>();
    Point start;
    Point end;

    public int findShortestMazePath(int[][] maze, Point start, Point end) {
        this.maze = maze;
        this.start = start;
        this.end = end;
        this.visited = new boolean[maze.length][maze[0].length];

        queue.offer(start);
        while (!queue.isEmpty()) {
            Point cur = queue.poll();
            //到达终点
            if (cur.x == end.x && cur.y == end.y) return cur.step;

            for (int i = 0; i < 4; i++) {
                int nextX = cur.x + dX[i];
                int nextY = cur.y + dY[i];
                if (isValid(nextX, nextY)) {
                    queue.offer(new Point(nextX, nextY, cur.step + 1));
                    visited[nextX][nextY] = true;
                }
            }
        }

        return -1;
    }

    private boolean isValid(int x, int y) {
        //判断边界
        if (x >= maze.length || x < 0 || y >= maze[0].length || y < 0) return false;
        if (maze[x][y] == 1) return false;
        return !visited[x][y];
    }


    public static void main(String[] args) {
        // 0为空地 1 为障碍物
        int[][] maze = {
                {0, 0, 0, 1},
                {0, 1, 0, 0},
                {0, 0, 1, 0},
                {0, 1, 0, 0},
                {0, 1, 0, 1}};
        Point start = new Point(0, 0);
        Point end = new Point(4, 2);

        System.out.println(new MazeDFS().findShortestMazePath(maze, start, end));
    }
}
